#include<bits/stdc++.h>
using namespace std;
int n,m,sum,dp[2005][2005],a[30][2];
char c[200005],b;
bool hw(int l,int r){
	while(l<r)
		if(c[l++]!=c[r--])return false;
	return true;
}
int main(){
	freopen("hw.in","r",stdin);
	freopen("hw.out","w",stdout);
	cin>>m>>n;
	cin>>c+1;
	c[0]='z'+1;
	for(int i=1;i<=m;i++){
		cin>>b;
		cin>>a[b-'a'][0]>>a[b-'a'][1];
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n-i;j++){
			dp[j][j+i]=dp[j+1][j+i-1]+min(min(a[c[j]-'a'][1]+a[c[j+i]-'a'][0],a[c[j]-'a'][0]+a[c[j+i]-'a'][1]),min(a[c[j]-'a'][0]+a[c[j+i]-'a'][0],a[c[j]-'a'][1]+a[c[j+i]-'a'][1]));
			if(hw(j,j+i))dp[j][j+i]=0;
			if(c[j]==c[j+i])dp[j][j+i]=min(dp[j][j+i],dp[j+1][j+i-1]);
		}
	}
	cout<<dp[0][n];
	return 0;
} 

